package j2024.j202411;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class j1114 {
    /**
     * 39. 组合总和
     * 给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，
     * 找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。
     *
     * candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。
     *
     * 对于给定的输入，保证和为 target 的不同组合数少于 150 个。
     * @param candidates
     * @param target
     * @return
     */
    List<List<Integer>> ret;
    List<Integer> path;
    int cou = 0;
    int t;
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        t = target;
        ret = new ArrayList<>();
        path = new ArrayList<>();
        dfs(candidates,0);
        return ret;
    }
    public void dfs(int[] candidates, int index) {
        if(cou == t){
            ret.add(new ArrayList<>(path));
            return;
        }else if(cou>t){
            return;
        }
        for (int i = 0; i < candidates.length; i++) {
            if(index>i){
                continue;
            }
            cou+=candidates[i];
            path.add(candidates[i]);
            dfs(candidates,index);
            path.remove(path.size()-1);
            cou-=candidates[i];
        }
    }
}
class kunann{
    /**
     * 52. N 皇后 II
     * n 皇后问题 研究的是如何将 n 个皇后放置在 n × n 的棋盘上，
     * 并且使皇后彼此之间不能相互攻击。
     *
     * 给你一个整数 n ，返回 n 皇后问题 不同的解决方案的数量。
     * @param n
     * @return
     */
    Set<Integer> col = new HashSet<>();
    Set<Integer> xiecol = new HashSet<>();
    Set<Integer> xierow = new HashSet<>();
    public int totalNQueens(int n) {
        //以行为变量
       return  Dfs(n,0);
    }
    public int Dfs(int n, int row){
        if(row == n){
            return 1;
        }
        int cou = 0;
        //遍历列
        for (int i = 0; i < n; i++) {
            if(col.contains(i)){
                continue;
            }
            //左上到右下 斜线每个位置满足 行与列之差相同
            int x1 = row-i;
            if(xiecol.contains(x1)){
                continue;
            }
            //右上到左下，斜线每个位置满足 行与列之和相同
            int x2 = row+i;
            if(xierow.contains(x2)){
                continue;
            }
            col.add(i);
            xiecol.add(x1);
            xierow.add(x2);
            cou+=Dfs(n,row+1);
            col.remove(i);
            xiecol.remove(x1);
            xierow.remove(x2);
        }
        return cou;
    }
}
